package Algorithm.dynamicProgramming.introduct;

/**
 * 674. 最长连续递增序列 https://leetcode.cn/problems/longest-continuous-increasing-subsequence
 * 题目简述：给定一个未经排序的整数数组，找到最长且连续相邻递增的子序列的长度。
 */
public class FindLengthOfLCIS {

    /**
     * 思路：动态规划
     * 1. 定义dp：dp[i]为以nums[i]结尾的最长递增序列
     * 2. 状态转移方程：当nums[i]小于等于nums[i-1]时，dp[i]=1；否则dp[i] = dp[i-1] + 1;
     * 3. 初始化：dp[0] = 1
     * 4. 遍历方式：从左向右依次遍历
     */
    public int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int max = 1;
        for(int i = 1;i < nums.length;i++) {
            if(nums[i] <= nums[i-1])
                dp[i] = 1;
            else {
                dp[i] = dp[i-1] + 1;
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }
}
